import java.util.Random;

public class Sort {

    /**
     * 直接插入排序
     * 时间复杂度:最坏情况下O(n^2) 逆序 最好情况O(n)有序
     * 对于直接插入排序来说数据越有序越快————>数据有序的情况下可考虑使用insertSort
     * 空间复杂度:
     * 稳定性: 稳定  稳定的排序可以变为不稳定的而不稳定的排序不可以变成稳定的排序
     * @param array
     */
    public void insertSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    public void shell(int[] array,int gap){
        int n = array.length;
        for (int i = gap; i < n; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度:O(n^1.3~n^1.5)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     * @param array
     */
    public void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);
    }


    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 选择排序
     * 时间复杂度:O(n^2)-->对数据不敏感
     * 空间复杂度:O(1)
     * 稳定性:不稳定排序
     * @param array
     */
    public  void selectSort(int[] array){
        int minIndex = 0;
        for (int i = 0; i < array.length; i++) {
            minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }


    /**
     * 时间复杂度:O(n*logn)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     * @param array
     */
    public void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length-1;
        while(end>=0){
            swap(array,end,0);
                shiftdown(array,0,end);
                end--;
        }
    }
    public void createBigHeap(int[] array){
        for(int parent = (array.length-1-1)/2;parent>=0;parent--){
            shiftdown(array,parent, array.length);
        }
    }
    private void shiftdown(int[] array,int parent,int len){
        int child = 2*parent+1;
        //起码保证有左孩子
        while(child<len){
            //有右孩子
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度:0(n^2)
     * 优化后的代码在有序的情况下时间复杂度为O(n)
     * 空间复杂度:O(1)
     * 稳定性:稳定
     * @param array
     */
    public void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(flg==false){
                break;
            }
        }
    }

    /**
     * 快速排序:Hoare法
     * 时间复杂度:O(N*logn)[理想情况：每次都为均分待排序序列]
     * 空间复杂度:O()
     * 稳定性:不稳定
     * @param array
     */
    public void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    public void quick(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    public int partitionHoare(int[] array,int start,int end){
        int i = start;
        int key = array[start];
        while(start<end){
            //注意为什么取=
            while(start<end&&array[end]>=key){
                end--;
            }
            while(start<end&&array[start]<=key){
                start++;
            }
            swap(array,start,end);
        }
        swap(array,i,start);
        return start;
    }

    /**
     * 快速排序:挖坑法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public int partitiondigpit(int[] array,int start,int end) {
        int key = array[start];
        while(start<end){
            while(start<end&&array[end]>=key){
                end--;
            }
            array[start] = array[end];
            while(start<end&&array[start]<=key){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }

    /**
     * 双指针法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public int partition(int[] array,int start,int end) {
        int prev = start;
        int cur = start+1;
        while(cur<=end){
            if(array[cur]<array[start]&&array[++prev]!=array[cur]){
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,start,prev);
        return prev;
    }
}
